home *** CD-ROM | disk | FTP | other *** search
/ Info-Mac 11 / Info-Mac_XI_Disc_1.cdr_ / Info-Mac XI Disc 1.cdr / Programs / Science & Math / MacEspresso 1.0 / espresso / primes.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-02-26  |  3.5 KB  |  162 lines  |  [TEXT/R*ch]
  1. #include "espresso.h"
  2.  
  3. static bool primes_consensus_special_cases();
  4. static pcover primes_consensus_merge();
  5. static pcover and_with_cofactor(); 
  6.  
  7.  
  8. /* primes_consensus -- generate primes using consensus */
  9. pcover primes_consensus(T)
  10. pcube *T;            /* T will be disposed of */
  11. {
  12.     register pcube cl, cr;
  13.     register int best;
  14.     pcover Tnew, Tl, Tr;
  15.  
  16.     if (primes_consensus_special_cases(T, &Tnew) == MAYBE) {
  17.     cl = new_cube();
  18.     cr = new_cube();
  19.     best = binate_split_select(T, cl, cr, COMPL);
  20.  
  21.     Tl = primes_consensus(scofactor(T, cl, best));
  22.     Tr = primes_consensus(scofactor(T, cr, best));
  23.     Tnew = primes_consensus_merge(Tl, Tr, cl, cr);
  24.  
  25.     free_cube(cl);
  26.     free_cube(cr);
  27.     free_cubelist(T);
  28.     }
  29.  
  30.     return Tnew;
  31. }
  32.  
  33. static bool 
  34. primes_consensus_special_cases(T, Tnew)
  35. pcube *T;            /* will be disposed if answer is determined */
  36. pcover *Tnew;            /* returned only if answer determined */
  37. {
  38.     register pcube *T1, p, ceil, cof=T[0];
  39.     pcube last;
  40.     pcover A;
  41.  
  42.     /* Check for no cubes in the cover */
  43.     if (T[2] == NULL) {
  44.     *Tnew = new_cover(0);
  45.     free_cubelist(T);
  46.     return TRUE;
  47.     }
  48.  
  49.     /* Check for only a single cube in the cover */
  50.     if (T[3] == NULL) {
  51.     *Tnew = sf_addset(new_cover(1), set_or(cof, cof, T[2]));
  52.     free_cubelist(T);
  53.     return TRUE;
  54.     }
  55.  
  56.     /* Check for a row of all 1's (implies function is a tautology) */
  57.     for(T1 = T+2; (p = *T1++) != NULL; ) {
  58.     if (full_row(p, cof)) {
  59.         *Tnew = sf_addset(new_cover(1), cube.fullset);
  60.         free_cubelist(T);
  61.         return TRUE;
  62.     }
  63.     }
  64.  
  65.     /* Check for a column of all 0's which can be factored out */
  66.     ceil = set_save(cof);
  67.     for(T1 = T+2; (p = *T1++) != NULL; ) {
  68.     INLINEset_or(ceil, ceil, p);
  69.     }
  70.     if (! setp_equal(ceil, cube.fullset)) {
  71.     p = new_cube();
  72.     (void) set_diff(p, cube.fullset, ceil);
  73.     (void) set_or(cof, cof, p);
  74.     free_cube(p);
  75.  
  76.     A = primes_consensus(T);
  77.     foreach_set(A, last, p) {
  78.         INLINEset_and(p, p, ceil);
  79.     }
  80.     *Tnew = A;
  81.     set_free(ceil);
  82.     return TRUE;
  83.     }
  84.     set_free(ceil);
  85.  
  86.     /* Collect column counts, determine unate variables, etc. */
  87.     massive_count(T);
  88.  
  89.     /* If single active variable not factored out above, then tautology ! */
  90.     if (cdata.vars_active == 1) {
  91.     *Tnew = sf_addset(new_cover(1), cube.fullset);
  92.     free_cubelist(T);
  93.     return TRUE;
  94.  
  95.     /* Check for unate cover */
  96.     } else if (cdata.vars_unate == cdata.vars_active) {
  97.     A = cubeunlist(T);
  98.     *Tnew = sf_contain(A);
  99.     free_cubelist(T);
  100.     return TRUE;
  101.  
  102.     /* Not much we can do about it */
  103.     } else {
  104.     return MAYBE;
  105.     }
  106. }
  107.  
  108. static pcover 
  109. primes_consensus_merge(Tl, Tr, cl, cr)
  110. pcover Tl, Tr;
  111. pcube cl, cr;
  112. {
  113.     register pcube pl, pr, lastl, lastr, pt;
  114.     pcover T, Tsave;
  115.  
  116.     Tl = and_with_cofactor(Tl, cl);
  117.     Tr = and_with_cofactor(Tr, cr);
  118.  
  119.     T = sf_new(500, Tl->sf_size);
  120.     pt = T->data;
  121.     Tsave = sf_contain(sf_join(Tl, Tr));
  122.  
  123.     foreach_set(Tl, lastl, pl) {
  124.     foreach_set(Tr, lastr, pr) {
  125.         if (cdist01(pl, pr) == 1) {
  126.         consensus(pt, pl, pr);
  127.         if (++T->count >= T->capacity) {
  128.             Tsave = sf_union(Tsave, sf_contain(T));
  129.             T = sf_new(500, Tl->sf_size);
  130.             pt = T->data;
  131.         } else {
  132.             pt += T->wsize;
  133.         }
  134.         }
  135.     }
  136.     }
  137.     free_cover(Tl);
  138.     free_cover(Tr);
  139.  
  140.     Tsave = sf_union(Tsave, sf_contain(T));
  141.     return Tsave;
  142. }
  143.  
  144.  
  145. static pcover
  146. and_with_cofactor(A, cof)
  147. pset_family A;
  148. register pset cof;
  149. {
  150.     register pset last, p;
  151.  
  152.     foreach_set(A, last, p) {
  153.     INLINEset_and(p, p, cof);
  154.     if (cdist(p, cube.fullset) > 0) {
  155.         RESET(p, ACTIVE);
  156.     } else {
  157.         SET(p, ACTIVE);
  158.     }
  159.     }
  160.     return sf_inactive(A);
  161. }
  162.